#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define NIL -1
struct Matrix{
int n;
int** value;
Matrix(int _n): n(_n){
this->value=new int*[this->n];
for(int i=0; i<this->n; ++i) this->value[i]=new int[this->n];
}
~Matrix(){
for(int i=0; i<this->n; ++i) delete value[i];
delete[] value;
}
Matrix& operator=(const Matrix& other) {
this->n=other.n;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j) this->Set(i, j, other.Value(i, j));
}
return *this;
}
int Value(int i, int j) const {
assert(i<this->n && j<this->n);
return value[i][j];
}
void Set(int i, int j, int x){
assert(i<this->n && j<this->n);
value[i][j]=x;
}
};
void PrintPI(Matrix* PI, int i, int j){
if(i==j) std::cout<<i<<' '<<std::endl;
else if(PI->Value(i, j)==NIL){
perror("NO ROUTE");
exit(1);
} else {
PrintPI(PI, i, PI->Value(i, j));
std::cout<<j<<' ';
}
}
Matrix ExtendShortestPaths(Matrix* L, Matrix* W){
int n=L->n;
Matrix nL(n);
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
nL.Set(i, j, INT_MAX);
for(int k=0; k<n; ++k){
int tmp=std::min(nL.Value(i, j), L->Value(i, k)+W->Value(k, j));
nL.Set(i, j,tmp);
}
}
}
return nL;
}
Matrix SquareMatrixMultiply(const Matrix* A, const Matrix* B){
int n=A->n;
Matrix C(n);
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
int tmp=0;
for(int k=0; k<n; ++k){
tmp+=A->Value(i, j)*B->Value(i, j);
C.Set(i, j, tmp);
}
}
}
return C;
}
Matrix ShowAllPairsShortestPaths(Matrix* W){
int n=W->n;
Matrix L=*W;
for(int m=2; m<n-2; ++m){
Matrix L=ExtendShortestPaths(&L, W);
}
return L;
}